package chapter03;

public class MaxDepth104 {
    /**
     * 深度优先遍历
     * 当前节点下 假设x左子树和右子树能给出其高度
     * 只需将左子树和右子树中最大高度+1返回就是x的高度
     * 递归出口
     *  1).x==null
     *      return 0
     *  2).leftHeight=process(x.left)
     *     rightHeight=process(x.right)
     *     return max(leftHeight,rightHeight)+1
     */
    public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode() {}
       TreeNode(int val) { this.val = val; }
       TreeNode(int val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
       }
   }

    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int leftHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        int maxHeight=Math.max(leftHeight,rightHeight);
        return maxHeight+1;
    }
}
